/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
 */
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;

        if(n == 0) return ret;

        // 查找左端点
        int left = 0, right = n - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            int x = nums[mid];
            if(x < target) left = mid + 1;
            else right = mid;
        }

        // 这个数组没有 target
        if(nums[left] != target) return ret;

        ret[0] = left;

        // 查找右端点
        left = 0; right = n - 1;
        while(left < right) {    
            int mid = left + (right - left + 1) / 2;
            int x = nums[mid];
            if(x <= target) left = mid;
            else right = mid - 1;
        }

        ret[1] = right;

        return ret;
    }
}